package clsFive1;

import edu.princeton.cs.algs4.StdOut;

public class LSD {
    public static void sort(String[] a, int W) {
        int N = a.length; // 数组长度
        int R = 256;      // 基数（ASCII 字符的可能值，0 到 255）
        String[] aux = new String[N]; // 辅助数组，用于临时存储排序结果

        for (int d = W - 1; d >= 0; d--) { // 从最低位（W-1）开始逐位排序
            int[] count = new int[R + 1]; // 频率数组，大小为 R+1（额外一个用于计算索引偏移）

            // **1. 计算频率**
            for (int i = 0; i < N; i++) {
                int fre = a[i].charAt(d) + 1;
                count[fre]++; // 第 d 位字符的频率，+1 是为了处理索引偏移
            }
            StdOut.println("打印 fre");
            printArrayInt(count);
            // **2. 将频率转换为索引**
            for (int r = 0; r < R; r++) {
                count[r + 1] += count[r]; //  累加频率，生成索引
            }
            StdOut.println("打印 index");
            printArrayInt(count);
            // **3. 根据索引将元素分类**
            for (int i = 0; i < N; i++) {
                aux[count[a[i].charAt(d)]++] = a[i];
            }

            // **4. 将分类好的元素写回原数组**
            for (int i = 0; i < N; i++) {
                a[i] = aux[i];
            }
            StdOut.println("打印 a");
            printArray(a);
        }
    }
    private static <T> void printArray(T[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
    private static <T> void printArrayInt(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
    public static void main(String[] args) {
        String[] data = {"dab", "cab", "lab", "fad", "bad", "dad", "ebb"};
        StdOut.println("数组为：");
        printArray(data);
        sort(data, 3);
    }
}